#include <stdio.h>
#include <stdlib.h>

/* 链表示例程序，不使用二级指针 */
typedef struct Student {
  int num;
  float score;
  struct Student *next;
} STU_RECORD;

/* 使用typedef给结构体类型起别名后，可以使用两种方式来表示结构体类型Student：

1. struct Student
2. STU_RECORD

两种表示方式是等价的。
*/

/* 从键盘输入创建链表，将链表头指针以函数返回值的形式返回 */
struct Student *create() {
  struct Student *head = NULL;
  struct Student *tail = NULL;
  int num;
  float score;
  scanf("%d", &num);
  scanf("%f", &score);
  while (num != 0) {
    // 为读入的记录创建
    struct Student *n = (struct Student *)malloc(sizeof(struct Student));
    n->num = num;
    n->score = score;
    n->next = NULL;
    if (head == NULL) { // 第一个结点
      head = n;
      tail = n;
    } else {
      tail->next = n;
      tail = n; // 尾指针向后移动
    }
    scanf("%d", &num);
    scanf("%f", &score);
  }
  return head;
}

/* 遍历链表并打印链表内容，传入的参数是链表头指针 */
void print_list(struct Student *head) {
  printf("-----\n");
  struct Student *p = head;
  float sum = 0;
  long count = 0;
  while (p != NULL) {
    printf("ID=%d, score=%.2f\n", p->num, p->score);
    sum += p->score;
    count++;
    p = p->next;
  }
  float avg = sum / count;
  printf("average score: %.2f\n", avg);
  printf("-----\n");
}

/* 删除、释放一个链表，将清空后的链表头指针以函数返回值的形式返回 */
STU_RECORD *delete_list(struct Student *head) {
  struct Student *p = head;
  while (p != NULL) {
    struct Student *tmp = p;
    p = p->next;
    free(tmp);
    tmp = NULL;
  }
  // 删除一个链表后，头结点指针清空为NULL
  return NULL;
}

/* 向链表头插入一条新记录，该操作会更新链表的头指针，将更新后的链表头指针以函数返回值的形式返回 */
STU_RECORD* insert_node_at_head(STU_RECORD *head, int num, float score) {
  // 新建节点
  struct Student *tmp = (struct Student *)malloc(sizeof(struct Student));
  tmp->num = num;
  tmp->score = score;
  tmp->next = NULL;
  // 将原来的头指针赋值给新插入结点的next
  tmp->next = head;
  // 将当前头指针head指向新创建的结点
  head = tmp;
  // 将新的头指针以函数返回值的形式返回给调用者
  return head;
}

/* 在链表的after_num学号的记录后面插入新的记录，如果没有找到，则在链表尾添加。
  因为在该函数中不会更新链表头结点指针，因此返回值可以是void。 */
void insert_after_node(STU_RECORD *head, int num, float score,
                       int after_num) {
  // 先定位after_num在哪儿
  struct Student *p = head;
  while (p != NULL) {
    if (after_num == p->num)
      break;
    p = p->next;
  }
  if (p != NULL) {
    // 在p之后插入
    // 新建节点
    struct Student *tmp = (struct Student *)malloc(sizeof(struct Student));
    tmp->num = num;
    tmp->score = score;
    tmp->next = NULL;
    // 加入链表
    tmp->next = p->next;
    p->next = tmp;
  } else {
    // 在链表尾插入
    // 先找到链表尾结点的指针
    struct Student *tail = head;
    while (tail->next != NULL) {
      tail = tail->next;
    }
    struct Student *tmp = (struct Student *)malloc(sizeof(struct Student));
    tmp->num = num;
    tmp->score = score;
    tmp->next = NULL;
    // 插入表尾
    tail->next = tmp;
  }
}

/* 从链表中删除指定学号num的学生。
*  如果待删除学号num的学生存储在表头结点，则需要修改链表头指针。
*  将删除后的新链表的头指针通过函数返回值返回调用者。
 */
STU_RECORD* delete_node(STU_RECORD *head, int num) {
  // 是否删除的是表头？
  if (head->num == num) { // 要删除表头的情况
    struct Student *tmp = head;
    // 将链表头指针移动到下一个结点
    head = head->next;
    // 将原来的结点删掉
    free(tmp);
    tmp = NULL;
  } else {
    // 待删除的结点一定是位于表头之后
    // 定位prev和p
    struct Student *prev = head;
    struct Student *p = prev->next;
    while (p != NULL) {
      if (p->num == num) {
        break;
      }
      prev = p;
      p = p->next;
    }
    if (p != NULL) {
      // 进行删除操作
      prev->next = p->next;
      free(p);
      p = NULL;
    }
  }
  return head; // 将当前的链表头指针通过函数返回值返回（对于第一种情况，该指针会发生变化）
}

/* 打印指定学号同学的成绩 */
void print_node(struct Student *head, int num) {
  struct Student *p = head;
  while (p != NULL) {
    if (p->num == num) {
      printf("ID=%d, score=%.2f\n", p->num, p->score);
    }
    p = p->next;
  }
}

int main(int argc, char const *argv[]) {
  struct Student *head;
  head = create();
  printf("The head of the linked list is %p\n", head);
  print_list(head);
  // 向链表头插入结点，新的链表头指针以函数返回值的形式返回
  head = insert_node_at_head(head, 10111, 100.0);
  print_list(head);
  // 向学号为10111的结点之后插入新结点
  insert_after_node(head, 101113, 77, 10111);
  printf("The head of the linked list is %p\n", head);
  print_list(head);
  // 打印学号为10103的学生的记录
  print_node(head, 10103);
  // 删除学号为10111的学生的记录，因为删除结点有可能造成头结点指针的变化，因此需要从函数返回值中更新head指针。
  printf("before: The head of the linked list is %p\n", head);
  head = delete_node(head, 10111);
  print_list(head);
  printf("after: The head of the linked list is %p\n", head);
  // 释放并删除整个链表
  head = delete_list(head);
  printf("After delete, head=%p\n", head);
  return 0;
}

/*

测试输入：

10100 100
10101 99
10102 98
10103 97
10104 96
0 0

*/